Many scheduling problems are NP-hard on classical computers. Using quantum parallelism and entanglement, a quantum schedule algorithm may be able to lead to an exponential improvement. The algorithm presented in this paper constructs a superposition of all schedules and a superposition of their makespans and then amplifies the one that corresponds to the solution. We perform $\mathcal{O}(\sqrt{2^{n+q}})$ Grover iterations. The time complexity of the quantum scheduling algorithm for an $R||C_{max}$ problem is $O(\sqrt{2^{n+q}})$ while the complexity of a classical algorithm is $\mathcal{O}(2^{m2^n})$.
展开▼
